package tree

import (
	"goqk/core/common"
	"goqk/core/crytography"
	"math"
	"time"
)

// BucketTree - 自定义bucket-tree
type BucketTree struct {
	MerkleRoot *MerkleNode
	Buckets    []MerkleNode
}

// MerkleNode - 梅克尔树节点
type MerkleNode struct {
	Owner    *MerkleNode
	Children []MerkleNode
	Hash     string
	Entries  []Entry
}

// Entry - 叶子节点上的Entry，用于存储数据
type Entry struct {
	Owner     *MerkleNode
	Hash      string
	Data      []byte
	TimeStamp time.Time
}

// Build - 构建bucket-tree
func (b *BucketTree) Build() error {
	b.MerkleRoot = &MerkleNode{Owner: nil}
	// 计算收敛
	aggWidth := int(math.Ceil(common.Sqrt(float64(Config.Capacity), float64(Config.Level-1))))
	// 创建节点
	b.buildNodes(Config.Level-1, aggWidth, b.MerkleRoot)

	return nil
}

// PushEntry - 放入预先定制的桶中
func (b *BucketTree) PushEntry(entry *Entry) *MerkleNode {
	// 放入预先定制的桶中
	bucketIndex := entry.TimeStamp.Nanosecond() % Config.Capacity
	bucket := b.Buckets[bucketIndex]
	// bucket.Entries = make(map[string]*Entry)
	// bucket.Entries[entry.Hash] = entry
	bucket.Entries = append(bucket.Entries, *entry)

	// 按时间排序
	b.sort(bucket.Entries, 0, len(bucket.Entries))

	// 重新计算所属bucket的hash
	var hash1 string
	for _, ent := range bucket.Entries {
		hash1 += ent.Hash
	}
	bucket.Hash = crytography.Hash([]byte(hash1))
	// // 重新计算所属node的hash
	// for _, bucket := range bucket.Owner.Buckets {
	// 	hash2 += bucket.Hash
	// }
	// bucket.Owner.Hash = crytography.Hash([]byte(hash2))

	// 从bucketNode开始，重新计算MerkleRoot
	b.RecalculateTreeHash(&bucket)

	return &bucket
}

// RecalculateTreeHash function
func (b *BucketTree) RecalculateTreeHash(node *MerkleNode) {
	// 到达根
	if node.Owner == nil {
		b.MerkleRoot = node
		return
	}

	// 计算merkle节点上的hash
	var str string
	for _, n := range node.Owner.Children {
		str += n.Hash
	}
	node.Owner.Hash = crytography.Hash([]byte(str))
	b.RecalculateTreeHash(node.Owner)
}

// 快速排序
func (b *BucketTree) sort(entries []Entry, left, right int) {
	// temp := entries[left]
	// p := left
	// i, j := left, right
	// for i <= j {
	// 	for j >= p && entries[j].TimeStamp.After(temp.TimeStamp) {
	// 		j--
	// 	}

	// 	if j >= p {
	// 		entries[p] = entries[j]
	// 		p = j
	// 	}

	// 	if entries[i].TimeStamp.After(temp.TimeStamp) && i <= p {
	// 		i++
	// 	}

	// 	if i <= p {
	// 		entries[p] = entries[i]
	// 		p = i
	// 	}
	// }

	// entries[p] = temp
	// if p-left > 1 {
	// 	b.sort(entries, left, p-1)
	// }
	// if right-p > 1 {
	// 	b.sort(entries, p+1, right)
	// }
}

func (b *BucketTree) buildNodes(depth int, aggWidth int, node *MerkleNode) {
	if depth < 1 {
		return
	}

	// 已达到叶子节点，构造桶
	if depth == 1 {
		for index := 0; index < aggWidth; index++ {
			b.Buckets = append(b.Buckets, MerkleNode{Owner: node})
		}
		b.MerkleRoot = node
		return
	}

	// 构造internal节点
	for i := 0; i < aggWidth; i++ {
		node.Children = append(node.Children, MerkleNode{Owner: node})
		b.buildNodes(depth-1, aggWidth, &node.Children[i])
	}
}
